package com.xk._02算法篇._08dynamicProgramming;

/**
 * @description: 最长公共子串
 * @author: xu
 * @date: 2022/10/20 13:55
 */
public class LCSSubString {
    public static void main(String[] args) {
        System.out.println(new LCSSubString().lcsSubStr("ABDCBA", "ABCBA"));
    }

    public int lcsSubStr(String str1, String str2) {
        if (str1 == null || str1.isEmpty()) return 0;
        if (str2 == null || str2.isEmpty()) return 0;
        char[] rowChars = str1.toCharArray();
        char[] colChars = str2.toCharArray();
        if (rowChars.length < colChars.length) {
            char[] tmp = rowChars;
            rowChars = colChars;
            colChars = tmp;
        }
        int[] dp = new int[colChars.length + 1];
        int max = 0;
        for (int row = 1; row <= rowChars.length; row++) {
            for (int col = colChars.length; col >= 1; col--) {
                if (rowChars[row - 1] != colChars[col - 1]) {
                    dp[col] = 0;
                } else {
                    dp[col] = dp[col-1] + 1;
                    max = Math.max(max, dp[col]);
                }
            }
        }
        return max;
    }

    // 动态数组
    // 时间：O(m*n)  空间：O(k) k = min{ str1.length(), str2.length }
    public int lcsSubStr2(String str1, String str2) {
        if (str1 == null || str1.isEmpty()) return 0;
        if (str2 == null || str2.isEmpty()) return 0;
        char[] rowChars = str1.toCharArray();
        char[] colChars = str2.toCharArray();
        if (rowChars.length < colChars.length) {
            char[] tmp = rowChars;
            rowChars = colChars;
            colChars = tmp;
        }
        int[] dp = new int[colChars.length + 1];
        int max = 0;
        for (int row = 1; row <= rowChars.length; row++) {
            int cur = 0;
            for (int col = 1; col <= colChars.length; col++) {
                int leftTop = cur;
                cur = dp[col];
                if (rowChars[row - 1] != colChars[col - 1]) {
                    dp[col] = 0;
                } else {
                    dp[col] = leftTop + 1;
                    max = Math.max(max, dp[col]);
                }
            }
        }
        return max;
    }

    // 动态数组
    // 时间：O(m*n)  空间：O(m*n)
    public int lcsSubStr1(String str1, String str2) {
        if (str1 == null || str1.isEmpty()) return 0;
        if (str2 == null || str2.isEmpty()) return 0;
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int[][] dp = new int[chars1.length + 1][chars2.length + 1];
        int max = 0;
        for (int i = 1; i <= chars1.length; i++) {
            for (int j = 1; j <= chars2.length; j++) {
                if (chars1[i - 1] != chars2[j - 1]) continue;
                dp[i][j] = dp[i-1][j-1] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

}
